package com.ctl.algorithm;

import java.util.*;

/**
 * <p>Title: Test</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2019</p>
 * <p>Company: www.ctl.com</p>
 * https://mp.weixin.qq.com/s/wraIMEVGz4GcNxe5WtxPRQ
 * 解数独-回溯算法解决
 * 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 9个 3x3 宫内只能出现一次。
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * 输入：board = [
 * ["5","3",".",".","7",".",".",".","."],
 * ["6",".",".","1","9","5",".",".","."],
 * [".","9","8",".",".",".",".","6","."],
 * ["8",".",".",".","6",".",".",".","3"],
 * ["4",".",".","8",".","3",".",".","1"],
 * ["7",".",".",".","2",".",".",".","6"],
 * [".","6",".",".",".",".","2","8","."],
 * [".",".",".","4","1","9",".",".","5"],
 * [".",".",".",".","8",".",".","7","9"]]
 * 输出：[
 * ["5","3","4","6","7","8","9","1","2"],
 * ["6","7","2","1","9","5","3","4","8"],
 * ["1","9","8","3","4","2","5","6","7"],
 * ["8","5","9","7","6","1","4","2","3"],
 * ["4","2","6","8","5","3","7","9","1"],
 * ["7","1","3","9","2","4","8","5","6"],
 * ["9","6","1","5","3","7","2","8","4"],
 * ["2","8","7","4","1","9","6","3","5"],
 * ["3","4","5","2","8","6","1","7","9"]]
 *
 * @author ctl
 * @version 1.1
 * @date 2023-02-07 17:28
 */


public class Sudoku9_9_3 {
    private static boolean isValid(String[][] board, String c, int row, int col) {
        for (int i = 0; i < 9; i++) {
            if (c.equals(board[row][i]) || c.equals(board[i][col])) {
                return false;
            }
            //int xStart=row/3*3;//0,3,6
            //int yStart=col/3*3;//0,3,6
            //i/3=0,0,0,1,1,1,2,2,2
            //i%3=0,1,2,0,1,2,0,1,2
            //board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] 刚好是3*3且是在小9格的范围
            //row0 col0,col1,col2  i=0,1,2
            //row1 col0,col1,col2  i=3,4,5
            //row2 col0,col1,col2  i=6,7,8
            if (board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3].equals(c)) {
                return false;
            }
        }
        return true;
    }

    private static boolean isValid(String[][] board, Point point) {
        int row = point.getX();
        int col = point.getY();
        String c = point.getArray().get(point.getCurrentIndex());
        return isValid(board, c, row, col);
    }


    /**
     * 输出二维数组
     *
     * @param array
     */
    private static void print9_9_array(String[][] array) {
        System.out.println();
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.deepToString(array[i]));
        }
    }

    /**
     * 点位只有一个被选那么先直接填充然后从待填充列表删除
     *
     * @param pointList
     * @param array9_9
     */
    private static void pointOneFill(List<Point> pointList, String[][] array9_9) {
        Iterator<Point> iterator = pointList.iterator();
        while (iterator.hasNext()) {
            Point next = iterator.next();
            if (next.getArray().size() == 1) {
                array9_9[next.getX()][next.getY()] = next.getArray().get(0);
                iterator.remove();
            }
        }
    }

    /**
     * 获取每个代填位置可以填充的数字列表(供回溯使用)
     *
     * @param blank
     * @param pointList
     * @param array9_9
     */
    private static void getPointArray(String blank, List<Point> pointList, String[][] array9_9) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (array9_9[i][j].equals(blank)) {
                    Point point = new Point().withX(i).withY(j);
                    pointList.add(point);
                    for (int k = 0; k < array9.length; k++) {
                        String canUse = array9[k];
                        if (isValid(array9_9, canUse, i, j)) {
                            point.getArray().add(canUse);
                        }
                    }
                }
            }
        }
        pointOneFill(pointList,array9_9);
        getPointMap();
    }

    static String[] array9 = new String[]{"1", "2", "3", "4", "5", "6", "7", "8", "9"};
    static int times = 0;

    private static boolean extracted(int row, int col) {
        ++times;
        if (row == 9) {
            return true;
        }
        if (col == 9) {
            return extracted(row + 1, 0);
        }

        if (!array9_9[row][col].equals(".")) {
            return extracted(row, col + 1);
        }
        Point point = pointMap.get(row + "_" + col);
        int length=point.getArray().size();
        for (int i = 0; i < length; i++) {
            point.setCurrentIndex(i);
            if (!isValid(array9_9, point)) {
                continue;
            }
            array9_9[row][col] = point.getArray().get(point.getCurrentIndex());
//            print9_9_array(array9_9);
            if (extracted(row, col)) {
                return true;
            }
            array9_9[row][col] = ".";
            point.setCurrentIndex(0);
        }
        return false;
    }

    static Map<String, Point> pointMap = new HashMap<>();

    private static Map<String, Point> getPointMap() {
        pointList.forEach(point -> pointMap.put(point.getX() + "_" + point.getY(), point));
        return pointMap;
    }

    static List<Point> pointList = new ArrayList<>();
    static String[][] array9_9 = new String[][]{{"5", "3", ".", ".", "7", ".", ".", ".", "."}, {"6", ".", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
    static String[][] array9_9_back = new String[][]{{"5", "3", ".", ".", "7", ".", ".", ".", "."}, {"6", ".", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};

    public static void main(String[] args) {
        String blank = ".";
        getPointArray(blank, pointList, array9_9);
        extracted(0, 0);
//        for (int i = 0; i < pointList.size(); i++) {
//            Point point = pointList.get(i);
//            array9_9[point.getX()][point.getY()] = point.getArray().get(point.getCurrentIndex());
//        }
        print9_9_array(array9_9);
        System.out.println("times="+times);
        System.out.println(pointList);

        array9_9 = new String[][]{{"5", "1", ".", ".", "7", ".", ".", ".", "."}, {"6", "2", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
        array9_9_back = new String[][]{{"5", "1", ".", ".", "7", ".", ".", ".", "."}, {"6", "2", ".", "1", "9", "5", ".", ".", "."}, {".", "9", "8", ".", ".", ".", ".", "6", "."}, {"8", ".", ".", ".", "6", ".", ".", ".", "3"}, {"4", ".", ".", "8", ".", "3", ".", ".", "1"}, {"7", ".", ".", ".", "2", ".", ".", ".", "6"}, {".", "6", ".", ".", ".", ".", "2", "8", "."}, {".", ".", ".", "4", "1", "9", ".", ".", "5"}, {".", ".", ".", ".", "8", ".", ".", "7", "9"}};
//        extracted(array9_9, pointList, 0, 0);
//        print9_9_array(array9_9);
//        print9_9_array(array9_9_back);
//        System.out.println(pointList);
    }


}

